Bus routes¶
Time: O(E + V); Space: O(E + V); hard
We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.
We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
Example 1:
Input: routes =
[
[1, 2, 7],
[3, 6, 7]
],
S = 1, T = 6 Output: 2
Explanation:
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Notes:
1 <= len(routes) <= 500.
1 <= len(routes[i]) <= 10^5.
0 <= routes[i][j] < 10 ^ 6.
1. Breadth First Search¶
Intuition Instead of thinking of the stops as nodes (of a graph), think of the buses as nodes. We want to take the least number of buses, which is a shortest path problem, conducive to using a breadth-first search.
Algorithm We perform a breadth first search on bus numbers. When we start at S, originally we might be able to board many buses, and if we end at T we may have many targets for our goal state.
One difficulty is to efficiently decide whether two buses are connected by an edge. They are connected if they share at least one bus stop. Whether two lists share a common value can be done by set intersection (HashSet), or by sorting each list and using a two pointer approach.
To make our search easy, we will annotate the depth of each node: info[0] = node, info[1] = depth.
[7]:
import collections
class Solution1(object):
"""
BFS
Time: Let N denote the number of buses, and bi be the number of stops on the iith bus.
To create the graph, in Python we do O(?(N?i)bi) work
(we can improve this by checking for which of r1, r2 is smaller),
while in Java we did a O(?bi*Logbi) sorting step, plus our searches are O(N?bi) work.
Our (breadth-first) search is on N nodes, and each node could have N edges, so it is O(N^2).
Space: O(N^2 +?bi) additional space complexity, the size of graph and routes.
"""
def numBusesToDestination(self, routes, S, T):
"""
:type routes: List[List[int]]
:type S: int
:type T: int
:rtype: int
"""
if S == T:
return 0
routes = list(map(set, routes))
graph = collections.defaultdict(set)
for i, r1 in enumerate(routes):
for j in range(i+1, len(routes)):
r2 = routes[j]
if any(r in r2 for r in r1):
graph[i].add(j)
graph[j].add(i)
seen, targets = set(), set()
for node, route in enumerate(routes):
if S in route:
seen.add(node)
if T in route:
targets.add(node)
queue = [(node, 1) for node in seen]
for node, depth in queue:
if node in targets:
return depth
for nei in graph[node]:
if nei not in seen:
seen.add(nei)
queue.append((nei, depth+1))
return -1
[8]:
s = Solution1()
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
assert s.numBusesToDestination(routes, S, T) == 2
[9]:
import collections
class Solution2(object):
"""
Time: O(|V|+|E|)
Space: O(|V|+|E|)
"""
def numBusesToDestination(self, routes, S, T):
"""
:type routes: List[List[int]]
:type S: int
:type T: int
:rtype: int
"""
if S == T:
return 0
to_route = collections.defaultdict(set)
for i, route in enumerate(routes):
for stop in route:
to_route[stop].add(i)
result = 1
q = [S]
lookup = set([S])
while q:
next_q = []
for stop in q:
for i in to_route[stop]:
for next_stop in routes[i]:
if next_stop in lookup:
continue
if next_stop == T:
return result
next_q.append(next_stop)
to_route[next_stop].remove(i)
lookup.add(next_stop)
q = next_q
result += 1
return -1
[10]:
s = Solution2()
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
assert s.numBusesToDestination(routes, S, T) == 2